package allHot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 15. 三数之和
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
 * 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 *
 * 思路：因为是三元组，所以可以将一个元素固定出来，然后剩下两个元素变量，将这两个元素变量再使用双指针法解决问题。
 *      使用双指针法的前提是原数组需要进行排序
 *
 *      核心方法：排序+双指针法
 * 该问题的关键在于高效寻找不重复的三元组，通过排序预处理和双指针的优化策略，可将时间复杂度降至 O(n²)，同时解决去重难题。
 * 步骤解析：
 * 数组排序
 * 排序是双指针法的基础，可简化重复判断逻辑，并利用有序性优化搜索
 * 固定首元素+双指针遍历
 *
 * 外层循环遍历数组，固定首元素 nums[i]
 * 内层使用双指针 left 和 right，分别指向 i+1 和数组末尾，寻找满足 nums[i] + nums[left] + nums[right] == 0 的组合
 * 去重逻辑
 * 首元素去重：若 nums[i] == nums[i-1]，跳过当前循环（需保证 i > 0）
 * 双指针去重：找到有效组合后，跳过所有与 nums[left]、nums[right] 相同的相邻元素
 * 剪枝优化
 * 若首元素 nums[i] > 0，因数组已排序，后续元素无法形成有效组合，直接终止循环
 */
public class L_015 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        // 通过for循环固定一个元素
        for (int i = 0; i < nums.length-2; i++) {
            // 如果首位的最小数字都大于0，则证明不存在和为0的三元组，直接返回
            if (nums[i] > 0){
                return result;
            }
            // 剪枝，避免重复的元素
            if (i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            // 使用双指针统计剩余的两个元素变量
            int left = i+1;
            int right = nums.length-1;
            while (left < right){
                int sum = nums[i] + nums[left] + nums[right];
                // 生成一个结果添加到结果集中
                if (sum == 0){
                    List<Integer> pair = new ArrayList<>();
                    pair.add(nums[i]);
                    pair.add(nums[left]);
                    pair.add(nums[right]);
                    result.add(pair);
                    // 剪枝，避免重复的元素
                    while (left < right && nums[left] == nums[left+1]){
                        left++;
                    }
                    while (left < right && nums[right] == nums[right-1]){
                        right--;
                    }
                    // 寻找到一个结果集后移动左右指针
                    left++;
                    right--;
                }else if (sum < 0){ // 证明最小值过小，left 需要大一点
                    left++;
                }else {
                    right--;
                }
            }
        }
        return result;
    }
}
